from typing import *


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.left = set()
        self.king = kingName
        self.children = DefaultDict(list)
        self.parent = {}

    def birth(self, parentName: str, childName: str) -> None:
        self.children[parentName].append(childName)
        self.parent[childName] = parentName

    def death(self, name: str) -> None:
        self.left.add(name)

    def getInheritanceOrder(self) -> List[str]:
        ans = []
        if self.king not in self.left:
            ans.append(self.king)

        cnts = Counter()

        def successor(x):
            if len(self.children[x]) == 0 or cnts[x] == len(self.children[x]):
                if x == self.king:
                    return None
                else:
                    return successor(self.parent[x])
            c = self.children[x][cnts[x]]
            if c not in self.left:
                ans.append(c)
            cnts[x] += 1
            return successor(c)

        successor(self.king)
        return ans
